﻿
//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为
//其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和
//复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点
//Node* copyRandomList(Node* head) {
//    Node* cur = head, * copyhead = nullptr;
//    Node* copy = copyhead;
//    map<Node*, Node*> m;
//    while (cur)
//    {
//        Node* newnode = new Node(cur->val);
//        if (copy == nullptr)
//            copy = copyhead = newnode;
//        else
//        {
//            copy->next = newnode;
//            copy = copy->next;
//        }
//        m[cur] = newnode;
//        cur = cur->next;
//    }
//    cur = head;
//    copy = copyhead;
//    while (cur)
//    {
//        if (cur->random == nullptr)
//            copy->random = nullptr;
//        else
//        {
//            copy->random = m[cur->random];
//        }
//        cur = cur->next;
//        copy = copy->next;
//    }
//    return copyhead;
//
//}

//给定一个单词列表words和一个整数k返回前k个出现次数最多的单词。
//返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字典顺序排序
//vector<string> topKFrequent(vector<string>& words, int k) {
//    map<string, int> m;
//    for (const auto& e : words)
//    {
//        m[e]++;
//    }
//    vector<pair<string, int>> v;
//    for (const auto& e : m)
//    {
//        v.push_back(e);
//    }
//    stable_sort(v.begin(), v.end(), Greator());
//    vector<string> res;
//    for (int i = 0; i < k; i++)
//    {
//        res.push_back(v[i].first);
//    }
//    return res;
//}

//输入一个英文句子，把句子中的单词(不区分大小写)按出现次数按从多到少把单词和次数在屏幕上输出来，次数一样的
//按照单词小写的字典序排序输出，要求能识别英文单词和句号
//struct Greator
//{
//    bool operator()(pair<string, int>m1, pair<string, int>m2)
//    {
//        return m1.second > m2.second;
//    }
//};
//int main() {
//    string s;
//    getline(cin, s);
//    int i = 0;
//    map<string, int> m;
//    while (s[i] != '.')
//    {
//        string word;
//        while (s[i] != ' ' && s[i] != '.')
//        {
//            if (i == 0)
//            {
//                word += s[i] + 32;
//            }
//            else
//            {
//                word += s[i];
//            }
//            i++;
//        }
//        m[word]++;
//        if (s[i] != '.')
//            i++;
//    }
//    vector<pair<string, int>> v(m.begin(), m.end());
//    stable_sort(v.begin(), v.end(), Greator());
//    for (auto& e : v)
//    {
//        cout << e.first << ":" << e.second << endl;
//    }
//}

//环形链表
//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
//ListNode* detectCycle(ListNode* head) {
//    ListNode* cur = head;
//    set<ListNode*> s;
//    while (cur)
//    {
//        if (s.count(cur))
//            return cur;
//        else
//        {
//            s.insert(cur);
//            cur = cur->next;
//        }
//    }
//    return nullptr;
//}